window.onload = function () {
  /**
   * 231. 2 的幂
   */
  console.log(isPowerOfTwo(2))

  /**
   * 547. 省份数量
   */
  console.log(findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

  /**
   * 52. N皇后 II
   */
  console.log(totalNQueens(4))
}

/**
 * 231. 2 的幂
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function (n) {
  return n > 0 && (n & (n - 1)) === 0;
};


/**
 * 547. 省份数量
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function (isConnected) {
  const provinces = isConnected.length;
  const visited = new Set();
  let circles = 0;
  for (let i = 0; i < provinces; i++) {
    if (!visited.has(i)) {
      dfs(isConnected, visited, provinces, i);
      circles++;
    }
  }
  return circles;
};

const dfs = (isConnected, visited, provinces, i) => {
  for (let j = 0; j < provinces; j++) {
    if (isConnected[i][j] == 1 && !visited.has(j)) {
      visited.add(j);
      dfs(isConnected, visited, provinces, j);
    }
  }
};


/**
 * 52. N皇后 II
 * @param {number} n
 * @return {number}
 */
 const backtrack = (n, row, columns, diagonals1, diagonals2) => {
  if (row === n) {
      return 1;
  } else {
      let count = 0;
      for (let i = 0; i < n; i++) {
          if (columns.has(i)) {
              continue;
          }
          const diagonal1 = row - i;
          if (diagonals1.has(diagonal1)) {
              continue;
          }
          const diagonal2 = row + i;
          if (diagonals2.has(diagonal2)) {
              continue;
          }
          columns.add(i);
          diagonals1.add(diagonal1);
          diagonals2.add(diagonal2);
          count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
          columns.delete(i);
          diagonals1.delete(diagonal1);
          diagonals2.delete(diagonal2);
      }
      return count;
  }
}
var totalNQueens = function(n) {
  const columns = new Set();
  const diagonals1 = new Set();
  const diagonals2 = new Set();
  return backtrack(n, 0, columns, diagonals1, diagonals2);
};